Levenshteinafstand

In inligtingsteorie word die Levenshteinafstand of redigeerafstand tussen twee karakterstringe gegee deur die minimum aantal bewerkings benodig om een string in 'n ander te transformeer, waar 'n bewerking 'n invoeging, skrapping, of vervanging is. Dit is vernoem na Vladimir Levenshtein, wat die afstand in 1965 oorweeg het. Dit is nuttig in toepassings wat moet bepaal hoe soortgelyk twee stringe is, soos speltoetsers en vertalingsgeheues.

Byvoorbeeld, die Levenshteinafstand tussen "kitten" en "sitting" is 3 omdat daar drie redigeerbewerkings nodig is om die een in die ander te verander, en daar is geen manier om dit in minder as drie verwerkings te doen nie:

• kitten

1. sitten (vervanging van 'k' met 's')
2. sittin (vervanging van 'e' met 'i')
3. sitting (byvoeg van 'g' aan die einde)

Dit kan as 'n veralgemening van die Hammingafstand gesien word wat vir stringe van dieselfde lengte gebruik word en wat slegs vervangingsbewerkings oorweeg. Daar is ook verdere veralgemenings van die Levenshteinafstand wat byvoorbeeld omruiling van twee karakters as 'n enkele verwerking hanteer.